给一个长度为 n 的序列 a,每次可以对这个序列的任意一个数 +1 或者 −1 代价都是 1,问使序列 a 变成(不严格)单调的最小代价。
n≤2000,ai≤109
这个题看起来有点难搞啊?
因为很难判断不符合单调的数是把它本身修改掉还是把它前面/后面修改掉更优。
题解
- 考虑最终的序列每个数肯定是原序列的某个值,但每个位置不能判断是它前面位置数还是后面的数
- 离散化 a[i]$
- 定义 dp[i][j]:考虑了前 i 个数,且第 i 个数为第 j 大的数的单调的最小值,暴力枚举 $dp[i-1]j转移到dp[i][j]的时间复杂度是O(n^3)$
- 考虑优化,dp[i][j]若是作为只上升的话,显然大于 j 的都不会影响到 dp[i][j] 的最小值,因为后面的肯定比前面的大。
- 同理最小可以得出
- 时间复杂度O(n2)
1 |
|